'''
  查找树：相当于实现python中的字典。其主要的功能如下：
        - Map() 创建一个新的空 `map`。
        - put(key，val) 向 `map` 中添加一个新的键值对。如果键已经在 `map` 中，那么用新值替换旧值。
        - get(key) 给定一个键，返回存储在 `map` 中的值，否则为 None。
        - del 使用 del map[key] 形式的语句从 `map` 中删除键值对。
        - len() 返回存储在映射中的键值对的数量。
        - in 返回 True 如果给定的键在 `map` 中。
'''
# 二叉搜索树
# 二叉搜索树特性在于左子树的值小于父节点的值，父节点的值小于右节点的值
class TreeNode:
    def __init__(self,key,val,left=None,right=None,parent=None,balanceFactor=0):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent
        self.balanceFactor = balanceFactor  # 这个在平衡二叉搜索树中会使用

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChild

    def isLeftChild(self):  # 判断该节点是不是左节点
        return self.parent and self.parent.leftChild == self

    def isRightChild(self):
        return self.parent and self.parent.rightChild == self

    def isRoot(self):
        return not self.parent

    def isLeaf(self):
        return not (self.leftChild and self.rightChild)

    def hasAnyChild(self):
        return (self.leftChild or self.rightChild)

    def hasBothChildren(self):
        return (self.leftChild and self.rightChild)

    def __iter__(self):
        if self:
            if self.hasLeftChild():
                for elem in self.leftChild:
                    yield elem
            yield self.key
            if self.hasRightChild():
                for elem in self.rightChild:
                    yield elem

    def replaceNodeData(self,key,value,lc,rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChild = rc
        # 改变了该节点的数值，但是其子节点的父亲没有指向自己
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChild.parent = self

    # 书中的源程序多此一举，因为已经是含有两个儿子了，所以一定有右儿子
    def findSuccessor(self):    # 寻找节点替换位置
        succ = None
        succ = self.rightChild.findMin()
        return succ
        # succ = None
        # if self.hasRightChild():
        #     succ = self.rightChild.findMin()
        # else:
        #     if self.parent:
        #         if self.isLeftChild():
        #             succ = self.parent
        #         else:
        #             self.parent.rightChild = None
        #             succ = self.parent.findSuccessor()
        #             self.parent.rightChild = self
        # return succ

    # 返回树的节点
    def findMin(self):
        current = self
        while current.hasLeftChild():
            current = current.leftChild
        return current

    # 删除上面返回的节点,按道理说该节点是不会有左子节点的，但是为了方便起见，我们考虑周全一下
    # def spliceOut(self):
    #     if self.isLeaf():   # 是叶子直接删
    #         if self.isLeftChild():
    #             self.parent.leftChild = None
    #         else:
    #             self.parent.rightChild = None
    #
    #     elif self.hasAnyChildren(): # 其实他只可能含有右子树，这个是考虑了很多不可能出现的情况
    #         if self.hasLeftChild():
    #             if self.isLeftChild():
    #                 self.parent.leftChild = self.leftChild
    #             else:
    #                 self.parent.rightChild = self.leftChild
    #             self.leftChild.parent = self.parent
    #         else:
    #             if self.isLeftChild():
    #                 self.parent.leftChild = self.rightChild
    #             else:
    #                 self.parent.rightChild = self.rightChild
    #             self.rightChild.parent = self.parent

    # 写一个简洁版的删除
    def spliceOut(self):
        if self.isLeaf():   # 是叶子则只可能是左儿子直接删
            self.parent.leftChild = None
        else:   # 自己只可能含有右儿子。
            if self.isLeftChild():
                self.parent.leftChild = self.rightChild
            else:
                self.parent.rightChild = self.rightChild
            self.rightChild.parent = self.parent


class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.size = 0

    def lengh(self):
        return self.size

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__()

    def put(self,key,val):
        if self.root:
            self._put(key,val,self.root)
            # print(val)
        else:
            self.root = TreeNode(key,val)
            print('qqq')
        #     print(val)
        # print(val)
        self.size = self.size + 1

    def _put(self,key,val,currentNode):
        print('aaaa')
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                self._put(key,val,currentNode.leftChild)
            else:
                currentNode.leftChild = TreeNode(key,val,parent=currentNode)    # 没有左子树就创建左子树
        # else:
        #     if currentNode.hasRightChild():
        #            self._put(key,val,currentNode.rightChild)
        #     else:
        #            currentNode.rightChild = TreeNode(key,val,parent=currentNode)
        elif key > currentNode.key:
            if currentNode.hasRightChild():
                self._put(key,val,currentNode.rightChild)
            else:
                currentNode.rightChild = TreeNode(key,val,parent=currentNode)   # 没有右子树创建右子树

        else:   # 不添加，修改值
            currentNode.payload = val
    # 内部的方法,里面直接由key和value，就能实现myZipTree['Plymouth'] = 55446这样的添加语句，就是一个添加语句
    def __setitem__(self, key, value):
        self.put(key,value)

    # 访问二叉搜索树，主要是输入键值,会返回结果
    def get(self,key):

        if self.root:
            # print(1)
            res = self._get(key,self.root)
            if res:
                # return res
                return res.payload,res.balanceFactor
            else:
                return None
        else:
            return None

    def _get(self,key,currentNode):
        if not currentNode:
            return None
        elif currentNode.key == key:
            return currentNode
        elif key < currentNode.key:
            return self._get(key,currentNode.leftChild)
        else:
            return self._get(key,currentNode.rightChild)

    def __getitem__(self, item):
        return self.get(item)

    # 这个主要是判断是否字典是否含有key这个键值
    def __contains__(self, item):
        if self._get(item,self.root):
            return True
        else:
            return False

    # 删除一个键值，首先搜索找到要删除的节点，先使用get方法找到要删除的节点。找到之后进行删除。注意删除之后的子节点如何操作
    # 思路：先找到，找到进行删除
    def delete(self,key):
        if self.size >= 1:  # 保证有树
            nodeToremove = self._get(key,self.root)
            if nodeToremove:
                self.remove(nodeToremove)
                self.size = self.size - 1
            else:
                raise KeyError('error, key not in tree')
        else:
            raise KeyError('error, key not in tree')

    def __delitem__(self, key):
        self.detele(key)

    def remove(self,currentNode):
        if currentNode.isLeaf():    # 叶子节点，可能只有一个根，可能含有父节点
            if currentNode.parent == None:  # 只有根节点
                self.root = None
            elif currentNode == currentNode.partent.leftChild:
                currentNode.parent.leftChild = None
            else:
                currentNode.parent.rightChild = None

        elif currentNode.hasBothChildren(): # 含有两个儿子
            succ = currentNode.findSuccessor()  # 找到替换该节点的节点
            succ.spliceOut()
            currentNode.key = succ.key
            currentNode.payload = succ.payload

        else:   # 含有一个儿子
            if currentNode.hasLeftChild():  # 含有左子树,自己是左子树，自己是右子树，自己是根节点
                if currentNode.isLeftChild():
                    currentNode.leftChild.parent = currentNode.parent
                    currentNode.parent.leftChild = currentNode.leftChild
                elif currentNode.isRightChild():
                    currentNode.leftChild.parent = currentNode.parent
                    currentNode.parent.rightChild = currentNode.leftChild
                else:   # 根节点
                    currentNode.replaceNodeData(currentNode.leftChild.key,currentNode.leftChild.payload,currentNode.leftChild.leftChild,currentNode.leftChild.rightChild)

            else:  # 含有右子树,自己是左子树，自己是右子树，自己是根节点
                if currentNode.isLeftChild():
                    currentNode.rightChild.parent = currentNode.parent
                    currentNode.parent.leftChild = currentNode.rightChild
                elif currentNode.isRightChild():
                    currentNode.rightChild.parent = currentNode.parent
                    currentNode.parent.rightChild = currentNode.rightChild
                else:   # 根节点
                    currentNode.replaceNodeData(currentNode.rightChild.key,currentNode.rightChild.payload,currentNode.rightChild.leftChild,currentNode.rightChild.rightChild)




#
# mytree = BinarySearchTree()
# mytree[3]="red"
# mytree[4]="blue"
# mytree[6]="yellow"
# mytree[2]="at"
# mytree[6]="yell"
# print(mytree[6])
# print(mytree[2])
# print(mytree[3])
# mytree.delete(3)
# print(mytree[3])